home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1995 August: Tool Chest / Dev.CD Aug 95 TC / Dev.CD Aug 95 TC.toast / Tool Chest / Development Tools & Languages / Dylan Related / Marlais / Marlais 0.5.9-portable sources / gc / allchblk.c next >
Encoding:
C/C++ Source or Header  |  1995-03-15  |  11.2 KB  |  368 lines  |  [TEXT/ttxt]
  1. /* 
  2.  * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
  3.  * Copyright (c) 1991-1994 by Xerox Corporation.  All rights reserved.
  4.  *
  5.  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
  6.  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
  7.  *
  8.  * Permission is hereby granted to use or copy this program
  9.  * for any purpose,  provided the above notices are retained on all copies.
  10.  * Permission to modify the code and to distribute modified code is granted,
  11.  * provided the above notices are retained, and a notice that the code was
  12.  * modified is included with the above copyright notice.
  13.  */
  14. /* Boehm, January 31, 1995 3:01 pm PST */
  15.  
  16. #define DEBUG
  17. #undef DEBUG
  18. #include <stdio.h>
  19. #include "gc_priv.h"
  20.  
  21.  
  22. /**/
  23. /* allocate/free routines for heap blocks
  24. /* Note that everything called from outside the garbage collector
  25. /* should be prepared to abort at any point as the result of a signal.
  26. /**/
  27.  
  28. /*
  29.  * Free heap blocks are kept on a list sorted by address.
  30.  * The hb_hdr.hbh_sz field of a free heap block contains the length
  31.  * (in bytes) of the entire block.
  32.  * Neighbors are coalesced.
  33.  */
  34.  
  35. # define MAX_BLACK_LIST_ALLOC (2*HBLKSIZE)
  36.         /* largest block we will allocate starting on a black   */
  37.         /* listed block.  Must be >= HBLKSIZE.            */
  38.  
  39. struct hblk * GC_hblkfreelist = 0;
  40.  
  41. struct hblk *GC_savhbp = (struct hblk *)0;  /* heap block preceding next */
  42.                      /* block to be examined by   */
  43.                      /* GC_allochblk.                */
  44.  
  45. void GC_print_hblkfreelist()
  46. {
  47.     struct hblk * h = GC_hblkfreelist;
  48.     word total_free = 0;
  49.     hdr * hhdr = HDR(h);
  50.     word sz;
  51.     
  52.     while (h != 0) {
  53.         sz = hhdr -> hb_sz;
  54.         GC_printf2("0x%lx size %lu ", (unsigned long)h, (unsigned long)sz);
  55.         total_free += sz;
  56.         if (GC_is_black_listed(h, HBLKSIZE) != 0) {
  57.              GC_printf0("start black listed\n");
  58.         } else if (GC_is_black_listed(h, hhdr -> hb_sz) != 0) {
  59.              GC_printf0("partially black listed\n");
  60.         } else {
  61.              GC_printf0("not black listed\n");
  62.         }
  63.         h = hhdr -> hb_next;
  64.         hhdr = HDR(h);
  65.     }
  66.     GC_printf1("Total of %lu bytes on free list\n", (unsigned long)total_free);
  67. }
  68.  
  69. /* Initialize hdr for a block containing the indicated size and     */
  70. /* kind of objects.                            */
  71. /* Return FALSE on failure.                        */
  72. static bool setup_header(hhdr, sz, kind, flags)
  73. register hdr * hhdr;
  74. word sz;    /* object size in words */
  75. int kind;
  76. unsigned char flags;
  77. {
  78.     register word descr;
  79.     
  80.     /* Add description of valid object pointers */
  81.       if (!GC_add_map_entry(sz)) return(FALSE);
  82.       hhdr -> hb_map = GC_obj_map[sz > MAXOBJSZ? 0 : sz];
  83.       
  84.     /* Set size, kind and mark proc fields */
  85.       hhdr -> hb_sz = sz;
  86.       hhdr -> hb_obj_kind = kind;
  87.       hhdr -> hb_flags = flags;
  88.       descr = GC_obj_kinds[kind].ok_descriptor;
  89.       if (GC_obj_kinds[kind].ok_relocate_descr) descr += WORDS_TO_BYTES(sz);
  90.       hhdr -> hb_descr = descr;
  91.       
  92.     /* Clear mark bits */
  93.       GC_clear_hdr_marks(hhdr);
  94.       
  95.     hhdr -> hb_last_reclaimed = (unsigned short)GC_gc_no;
  96.     return(TRUE);
  97. }
  98.  
  99. /*
  100.  * Allocate (and return pointer to) a heap block
  101.  *   for objects of size sz words.
  102.  *
  103.  * NOTE: We set obj_map field in header correctly.
  104.  *       Caller is resposnsible for building an object freelist in block.
  105.  *
  106.  * We clear the block if it is destined for large objects, and if
  107.  * kind requires that newly allocated objects be cleared.
  108.  */
  109. struct hblk *
  110. GC_allochblk(sz, kind, flags)
  111. word sz;
  112. int kind;
  113. unsigned char flags;  /* IGNORE_OFF_PAGE or 0 */
  114. {
  115.     register struct hblk *thishbp;
  116.     register hdr * thishdr;        /* Header corr. to thishbp */
  117.     register struct hblk *hbp;
  118.     register hdr * hhdr;        /* Header corr. to hbp */
  119.     struct hblk *prevhbp;
  120.     register hdr * phdr;        /* Header corr. to prevhbp */
  121.     signed_word size_needed;    /* number of bytes in requested objects */
  122.     signed_word size_avail;    /* bytes available in this block    */
  123.     bool first_time = TRUE;
  124.  
  125.     size_needed = HBLKSIZE * OBJ_SZ_TO_BLOCKS(sz);
  126.  
  127.     /* search for a big enough block in free list */
  128.     hbp = GC_savhbp;
  129.     hhdr = HDR(hbp);
  130.     for(;;) {
  131.  
  132.         prevhbp = hbp;
  133.         phdr = hhdr;
  134.         hbp = (prevhbp == 0? GC_hblkfreelist : phdr->hb_next);
  135.         hhdr = HDR(hbp);
  136.  
  137.         if( prevhbp == GC_savhbp && !first_time) {
  138.             return(0);
  139.         }
  140.  
  141.         first_time = FALSE;
  142.  
  143.         if( hbp == 0 ) continue;
  144.  
  145.         size_avail = hhdr->hb_sz;
  146.         if (size_avail < size_needed) continue;
  147.         /* If the next heap block is obviously better, go on.    */
  148.         /* This prevents us from disassembling a single large block */
  149.         /* to get tiny blocks.                    */
  150.         {
  151.           signed_word next_size;
  152.           
  153.           thishbp = hhdr -> hb_next;
  154.           if (thishbp == 0) thishbp = GC_hblkfreelist; 
  155.           thishdr = HDR(thishbp);
  156.           next_size = (signed_word)(thishdr -> hb_sz);
  157.           if (next_size < size_avail
  158.               && next_size >= size_needed
  159.               && !GC_is_black_listed(thishbp, (word)size_needed)) {
  160.               continue;
  161.           }
  162.         }
  163.         if ( kind != UNCOLLECTABLE &&
  164.              (kind != PTRFREE || size_needed > MAX_BLACK_LIST_ALLOC)) {
  165.           struct hblk * lasthbp = hbp;
  166.           ptr_t search_end = (ptr_t)hbp + size_avail - size_needed;
  167.           word orig_avail = size_avail;
  168.           signed_word eff_size_needed = ((flags & IGNORE_OFF_PAGE)?
  169.                               HBLKSIZE
  170.                               : size_needed);
  171.           
  172.           
  173.           while ((ptr_t)lasthbp <= search_end
  174.                  && (thishbp = GC_is_black_listed(lasthbp,
  175.                                        (word)eff_size_needed))) {
  176.             lasthbp = thishbp;
  177.           }
  178.           size_avail -= (ptr_t)lasthbp - (ptr_t)hbp;
  179.           thishbp = lasthbp;
  180.           if (size_avail >= size_needed) {
  181.             if (thishbp != hbp && GC_install_header(thishbp)) {
  182.               /* Split the block at thishbp */
  183.                   thishdr = HDR(thishbp);
  184.                   /* GC_invalidate_map not needed, since we will    */
  185.                   /* allocate this block.                */
  186.               thishdr -> hb_next = hhdr -> hb_next;
  187.               thishdr -> hb_sz = size_avail;
  188.               hhdr -> hb_sz = (ptr_t)thishbp - (ptr_t)hbp;
  189.               hhdr -> hb_next = thishbp;
  190.           /* Advance to thishbp */
  191.               prevhbp = hbp;
  192.               phdr = hhdr;
  193.               hbp = thishbp;
  194.               hhdr = thishdr;
  195.         }
  196.           } else if (size_needed > BL_LIMIT
  197.                      && orig_avail - size_needed > BL_LIMIT) {
  198.             /* Punt, since anything else risks unreasonable heap growth. */
  199.             WARN("Need to allocated blacklisted block at %ld\n", (word)hbp);
  200.             thishbp = hbp;
  201.             size_avail = orig_avail;
  202.           } else if (size_avail == 0
  203.                    && size_needed == HBLKSIZE
  204.                    && prevhbp != 0) {
  205. #        ifndef FIND_LEAK
  206.                 static unsigned count = 0;
  207.                 
  208.                 /* The block is completely blacklisted.  We need     */
  209.                 /* to drop some such blocks, since otherwise we spend */
  210.                 /* all our time traversing them if pointerfree    */
  211.                 /* blocks are unpopular.                */
  212.               /* A dropped block will be reconsidered at next GC.    */
  213.               if ((++count & 3) == 0) {
  214.                 /* Allocate and drop the block */
  215.                   if (GC_install_counts(hbp, hhdr->hb_sz)) {
  216.                     phdr -> hb_next = hhdr -> hb_next;
  217.                     (void) setup_header(
  218.                           hhdr,
  219.                             BYTES_TO_WORDS(hhdr->hb_sz - HDR_BYTES),
  220.                             PTRFREE, 0); /* Cant fail */
  221.                       if (GC_debugging_started) {
  222.                           BZERO(hbp + HDR_BYTES, hhdr->hb_sz - HDR_BYTES);
  223.                       }
  224.                     if (GC_savhbp == hbp) GC_savhbp = prevhbp;
  225.                   }
  226.                 /* Restore hbp to point at free block */
  227.                   hbp = prevhbp;
  228.                   hhdr = phdr;
  229.                   if (hbp == GC_savhbp) first_time = TRUE;
  230.               }
  231. #        endif
  232.           }
  233.         }
  234.         if( size_avail >= size_needed ) {
  235.         /* found a big enough block       */
  236.         /* let thishbp --> the block      */
  237.         /* set prevhbp, hbp to bracket it */
  238.             thishbp = hbp;
  239.             thishdr = hhdr;
  240.             if( size_avail == size_needed ) {
  241.             hbp = hhdr->hb_next;
  242.             hhdr = HDR(hbp);
  243.             } else {
  244.             hbp = (struct hblk *)
  245.                 (((word)thishbp) + size_needed);
  246.             if (!GC_install_header(hbp)) continue;
  247.             hhdr = HDR(hbp);
  248.             GC_invalidate_map(hhdr);
  249.             hhdr->hb_next = thishdr->hb_next;
  250.             hhdr->hb_sz = size_avail - size_needed;
  251.             }
  252.         /* remove *thishbp from hblk freelist */
  253.             if( prevhbp == 0 ) {
  254.             GC_hblkfreelist = hbp;
  255.             } else {
  256.             phdr->hb_next = hbp;
  257.             }
  258.         /* save current list search position */
  259.             GC_savhbp = hbp;
  260.         break;
  261.         }
  262.     }
  263.     
  264.     /* Notify virtual dirty bit implementation that we are about to write. */
  265.         GC_write_hint(thishbp);
  266.     
  267.     /* Add it to map of valid blocks */
  268.         if (!GC_install_counts(thishbp, (word)size_needed)) return(0);
  269.         /* This leaks memory under very rare conditions. */
  270.             
  271.     /* Set up header */
  272.         if (!setup_header(thishdr, sz, kind, flags)) {
  273.             GC_remove_counts(thishbp, (word)size_needed);
  274.             return(0); /* ditto */
  275.         }
  276.         
  277.     /* Clear block if necessary */
  278.     if (GC_debugging_started
  279.         || sz > MAXOBJSZ && GC_obj_kinds[kind].ok_init) {
  280.         BZERO(thishbp + HDR_BYTES,  size_needed - HDR_BYTES);
  281.     }
  282.     
  283.     return( thishbp );
  284. }
  285.  
  286. struct hblk * GC_freehblk_ptr = 0;  /* Search position hint for GC_freehblk */
  287.  
  288. /*
  289.  * Free a heap block.
  290.  *
  291.  * Coalesce the block with its neighbors if possible.
  292.  *
  293.  * All mark words are assumed to be cleared.
  294.  */
  295. void
  296. GC_freehblk(p)
  297. register struct hblk *p;
  298. {
  299. register hdr *phdr;    /* Header corresponding to p */
  300. register struct hblk *hbp, *prevhbp;
  301. register hdr *hhdr, *prevhdr;
  302. register signed_word size;
  303.  
  304.     /* GC_savhbp may become invalid due to coalescing.  Clear it. */
  305.     GC_savhbp = (struct hblk *)0;
  306.  
  307.     phdr = HDR(p);
  308.     size = phdr->hb_sz;
  309.     size = HBLKSIZE * OBJ_SZ_TO_BLOCKS(size);
  310.     GC_remove_counts(p, (word)size);
  311.     phdr->hb_sz = size;
  312.     GC_invalidate_map(phdr);
  313.     prevhbp = 0;
  314.     
  315.     /* The following optimization was suggested by David Detlefs.    */
  316.     /* Note that the header cannot be NIL, since there cannot be an    */
  317.     /* intervening  call to GC_freehblk without resetting        */
  318.     /* GC_freehblk_ptr.                            */
  319.     if (GC_freehblk_ptr != 0 &&
  320.         HDR(GC_freehblk_ptr)->hb_map == GC_invalid_map &&
  321.         (ptr_t)GC_freehblk_ptr < (ptr_t)p) {
  322.       hbp = GC_freehblk_ptr;
  323.     } else {
  324.       hbp = GC_hblkfreelist;
  325.     };
  326.     hhdr = HDR(hbp);
  327.  
  328.     while( (hbp != 0) && (hbp < p) ) {
  329.     prevhbp = hbp;
  330.     prevhdr = hhdr;
  331.     hbp = hhdr->hb_next;
  332.     hhdr = HDR(hbp);
  333.     }
  334.     GC_freehblk_ptr = prevhbp;
  335.     
  336.     /* Check for duplicate deallocation in the easy case */
  337.       if (hbp != 0 && (ptr_t)p + size > (ptr_t)hbp
  338.         || prevhbp != 0 && (ptr_t)prevhbp + prevhdr->hb_sz > (ptr_t)p) {
  339.         GC_printf1("Duplicate large block deallocation of 0x%lx\n",
  340.                (unsigned long) p);
  341.         GC_printf2("Surrounding free blocks are 0x%lx and 0x%lx\n",
  342.                   (unsigned long) prevhbp, (unsigned long) hbp);
  343.       }
  344.  
  345.     /* Coalesce with successor, if possible */
  346.       if( (((word)p)+size) == ((word)hbp) ) {
  347.     phdr->hb_next = hhdr->hb_next;
  348.     phdr->hb_sz += hhdr->hb_sz;
  349.     GC_remove_header(hbp);
  350.       } else {
  351.     phdr->hb_next = hbp;
  352.       }
  353.  
  354.     
  355.     if( prevhbp == 0 ) {
  356.     GC_hblkfreelist = p;
  357.     } else if( (((word)prevhbp) + prevhdr->hb_sz)
  358.                  == ((word)p) ) {
  359.       /* Coalesce with predecessor */
  360.     prevhdr->hb_next = phdr->hb_next;
  361.     prevhdr->hb_sz += phdr->hb_sz;
  362.     GC_remove_header(p);
  363.     } else {
  364.     prevhdr->hb_next = p;
  365.     }
  366. }
  367.  
  368.